#include "algorithm"
#include "TextComparer.h"
#include "..\Common\Utility.h"

namespace TextDiffAlgo
{
	std::string tPoint::toString()
	{
		std::string str;
		str.clear();
		str += ("(" + Utility::IntToString(x) + ", " + Utility::IntToString(y) + ")");
		return str;
	}

	int TextComparer::getV(Vector2D<int> arr, int i, int j)
	{
		if (i >= arr.vv2.size() || j >= arr.vv2[i].size()) {
			return 0;
		}
		return arr.vv2[i][j];
	}

	Vector2D<int> TextComparer::getMinSetpArr(Vector2D<int> miarr, Vector2D<bool> barr)
	{
		Vector2D<int> iarr;
		iarr.resize(miarr.vv2.size(), miarr.vv2[0].size());

		for (int i = iarr.vv2.size() - 1; i >= 0; i--) {
			for (int j = iarr.vv2[i].size() - 1; j >= 0; j--) {
				if (barr.vv2[i][j]) {
					iarr.vv2[i][j] = getV(iarr, i + 1, j + 1) + 1;
				} else if (getV(miarr, i, j + 1) >= getV(miarr, i + 1, j)) {
					iarr.vv2[i][j] = getV(iarr, i, j + 1);
				} else {
					iarr.vv2[i][j] = getV(iarr, i + 1, j) + 1;
				}
			}
		}
		return iarr;
	}

	Vector2D<int> TextComparer::getSetpPathArr(Vector2D<bool> barr)
	{
		Vector2D<int> iarr;
		iarr.resize(barr.vv2.size(), barr.vv2[0].size());

		for (int i = barr.vv2.size() - 1; i >= 0; i--) {
			for (int j = barr.vv2[0].size() - 1; j >= 0; j--) {
				int v_i_j = (barr.vv2[i][j] ? 1 : 0);
				int n_i_1_j_1 = ((i + 1 >= iarr.vv2.size() || j + 1 >= iarr.vv2[i].size()) ? 0 : iarr.vv2[i + 1][j + 1]);
				int n_i_1_j = i + 1 >= iarr.vv2.size() ? 0 : iarr.vv2[i + 1][j];
				int n_i_j_1 = j + 1 >= iarr.vv2[i].size() ? 0 : iarr.vv2[i][j + 1];
				int v_n_1_1 = v_i_j + n_i_1_j_1;

				iarr.vv2[i][j] = ((v_n_1_1 > n_i_1_j) ? ((v_n_1_1 > n_i_j_1) ? v_n_1_1 : n_i_j_1) : ((n_i_1_j > n_i_j_1) ? n_i_1_j : n_i_j_1));
			}
		}
		return iarr;
	}

	Vector2D<bool> TextComparer::getCompareBoolArray(std::string source, std::string compareTo)
	{
		Vector2D<bool> comps;
		ASSERT((!compareTo.empty() && !source.empty()), "One of the text string is empty.");
		comps.resize(compareTo.length(), source.length());

		for (int i = 0; i < compareTo.length(); i++) {
			for (int j = 0; j < source.length(); j++) {
				comps.vv2[i][j] = (compareTo[i] == source[j]);
			}
		}
		return comps;
	}

	TextDiffAlgo::tPoint TextComparer::getNext(tPoint p, Vector2D<int> miarr, Vector2D<int> diarr, Vector2D<bool> barr)
	{
		if (p.getX() >= barr.vv2.size() || p.getY() >= barr.vv2[p.getX()].size()) {
			return tPoint(INF, INF);
		}
		if (barr.vv2[p.getX()][p.getY()]) {
			return tPoint(p.getX() + 1, p.getY() + 1);
		}

		std::list<tPoint> pointList;
		int Min = -1;
		for (int i = p.getX(); i < barr.vv2.size(); i++) {
			for (int j = p.getY(); j < barr.vv2[i].size(); j++) {
				if (miarr.vv2[i][j] != miarr.vv2[p.getX()][p.getY()]) {
					break;
				}

				if (barr.vv2[i][j] && miarr.vv2[i][j] == miarr.vv2[p.getX()][p.getY()]) {
					if (Min == -1 || diarr.vv2[i][j] < Min) {
						Min = diarr.vv2[i][j];
					}
					pointList.push_back(tPoint(i, j));
				}
			}
		}
		if (pointList.size() > 0) {
			std::list<tPoint> removeList;
			for (std::list<tPoint>::iterator it = pointList.begin(), tmpit; it != pointList.end(); it++) {
				if (diarr.vv2[it->getX()][it->getY()] > Min) {
					tmpit = it;
					it++;
					pointList.erase(tmpit);
				}
			}

			if (pointList.size() > 0) {
				return *pointList.begin();
			}
		}

		return tPoint(INF, INF);
	}

	std::list<TextDiff> TextComparer::calcDiffs(tPoint startPoint, Vector2D<bool> barr, Vector2D<int> miarr, Vector2D<int> diarr)
	{
		if (startPoint == tPoint(INF, INF)) {
			return std::list<TextDiff>();
		}

		std::list<TextDiff> diffList;
		if (startPoint.getX() != 0) {
			diffList.push_back(TextDiff(TextDiff::DiffType::TYPE_INSERTED, 0, startPoint.getX()));
		}
		if (startPoint.getY() != 0) {
			diffList.push_back(TextDiff(TextDiff::DiffType::TYPE_DELETED, 0, startPoint.getY()));
		}

		tPoint next = getNext(startPoint, miarr, diarr, barr);

		while (next != tPoint(INF, INF)) {
			if (!barr.vv2[startPoint.getX()][startPoint.getY()]) {
				if (startPoint.getX() != next.getX()) {
					diffList.push_back(TextDiff(TextDiff::DiffType::TYPE_INSERTED, startPoint.getX(), next.getX() - startPoint.getX()));
				}
				if (startPoint.getY() != next.getY()) {
					diffList.push_back(TextDiff(TextDiff::DiffType::TYPE_DELETED, startPoint.getY(), next.getY() - startPoint.getY()));
				}
			}
			startPoint = next;
			next = getNext(startPoint, miarr, diarr, barr);
		}

		if (startPoint.getX() != barr.vv2.size()) {
			diffList.push_back(TextDiff(TextDiff::DiffType::TYPE_INSERTED, startPoint.getX(), barr.vv2.size() - startPoint.getX()));
		}
		if (startPoint.getY() != barr.vv2[0].size()) {
			diffList.push_back(TextDiff(TextDiff::DiffType::TYPE_DELETED, startPoint.getY(), barr.vv2[0].size() - startPoint.getY()));
		}

		return diffList;
	}

	std::list<TextDiff> TextComparer::compare(std::string source, std::string compareTo)
	{
		if (source.empty() || compareTo.empty()) {
			return std::list<TextDiff>();
		}
		Vector2D<bool> barr = getCompareBoolArray(source, compareTo);
		Vector2D<int> miarr = getSetpPathArr(barr);
		Vector2D<int> diarr = getMinSetpArr(miarr, barr);
		std::list<tPoint> pointList;
		int maxJ = -1;
		for (int i = 0; i < barr.vv2.size(); i++) {
			int tmpMaxJ = -1;
			for (int j = 0; j < barr.vv2[i].size(); j++) {
				if (j > maxJ && maxJ != -1) {
					break;
				}
				if (barr.vv2[i][j]) {
					if (tmpMaxJ == -1) {
						tmpMaxJ = j;
					}
					pointList.push_back(tPoint(i, j));
				}
			}
			if (tmpMaxJ != -1) {
				maxJ = tmpMaxJ;
			}
		}

		int Max = 0;
		int minStep = -1;
		for (std::list<tPoint>::iterator it = pointList.begin(); it != pointList.end(); it++) {
			if (miarr.vv2[it->getX()][it->getY()] > Max) {
				Max = miarr.vv2[it->getX()][it->getY()];
			}
		}
		for (std::list<tPoint>::iterator it = pointList.begin(); it != pointList.end(); it++) {
			if ((minStep == -1) || (miarr.vv2[it->getX()][it->getY()] >= Max && diarr.vv2[it->getX()][it->getY()] < minStep)) {
				minStep = diarr.vv2[it->getX()][it->getY()];
			}
		}

		for (std::list<tPoint>::iterator it = pointList.begin(), tmpit; it != pointList.end(); it++) {
			if (miarr.vv2[it->getX()][it->getY()] < Max || diarr.vv2[it->getX()][it->getY()] > minStep) {
				tmpit = it;
				it++;
				pointList.erase(tmpit);
			}
		}

		std::list<TextDiff> diffList = calcDiffs((pointList.size() >= 1 ? *pointList.begin() : tPoint(INF, INF)), barr, miarr, diarr);
		return diffList;
	}
}
